﻿#ifndef SparseGraph_h__
#define SparseGraph_h__

/********************************************************************
	创建于:		2011/03/19
	创建于:		19:3:2011   22:45
	基本文件:	SparseGraph
	文件扩展:	h
	作者:		王凯
	
	目的:		该代码主要思想来自于Mat先生的SparseGraph。
				该类为模板定义的模板类，对图数据结构的封装，提供各种常用操作。
*********************************************************************/

#include <vector>
#include <list>
#include <ostream>
#include <fstream>
#include <cassert>

#include "2D/Vector2D.h"//来自mat先生
#include "misc/utils.h"//来自mat先生
#include "NodeTypeEnumerations.h"//来自mat先生

template<typename node_type, typename edge_type>
class SparseGraph
{
public:
	//一些需要用到的类型定义
	typedef	node_type				NodeType;
	typedef	edge_type				EdgeType;

	typedef	std::vector<node_type>	NodeVector;
	typedef	std::list<edge_type>	EdgeList;
	typedef	std::vector<EdgeList>	EdgeListVector;

private:
	//顶点集
	NodeVector		m_Nodes;

	//边集
	EdgeListVector	m_Edges;

	//标记是否为有向图
	bool m_bDigraph;

	//下一个顶点的索引
	int m_iNextNodeIndex;

	//返回该条边时候已经出现在图中
	//该方法用在判断是否重复增加边
	bool UniqueEdge(int from, int to)const;

	//剔除无效的边
	void CullInvalidEdges();
public:
	//构造函数
	SparseGraph(bool digraph):m_bDigraph(digraph),
		m_iNextNodeIndex(0){}
	~SparseGraph(){}

	//const的GetNode
	const NodeType& GetNode(int idx)const;
	//non-const的GetNode
	NodeType& GetNode(int idx);

	//const的GetEdge
	const EdgeType& GetEdge(int from, int to)const;
	//non-const的GetEdge
	EdgeType& GetEdge(int from, int to);

	//返回下一个空缺的顶点的索引
	//注意：不能在未插入任何值前,
	//通过该方法获取索引然后赋予顶点
	int GetNextFreeNodeIndex()const{ return m_iNextNodeIndex;}

	//增加顶点，并返回该点索引
	int AddNode(NodeType node);
	
	//通过使该点索引变为invalid_node_index从而达到“删除”的目的
	void RemoveNode(int idx);

	//该方法用于增加边，并确保每次增加的边都是有效值
	//该方法会判断图是否是有向图，如果不是有向图，该
	//方法会自动增加反向边
	void AddEdge(EdgeType edge);

	//删除从from到to的边（如果有），如果不是有向图会
	//自动删除相反方向的边
	void RemoveEdge(int from, int to);

	//设置对应边得权值（如果有）
	void SetEdgeCost(int from, int to, double cost);

	//返回顶点数量
	//注意：返回值不能表示有多少有效顶点数量，如果需要
	//返回有效顶点数量，请使用NumActiveNodes函数
	int NumNodes()const{ return m_Nodes.size();}

	//返回有效的顶点数量
	int NumActiveNodes()const
	{
		int count = 0;
		//忽略无效索引的顶点
		for(int i = 0; i < (int)m_Nodes.size(); ++i) if(m_Nodes[i].Index() != invalid_node_index) count++;
		return count;
	}

	//返回边的数量
	int NumEdges()const
	{
		int tot = 0;
		for(EdgeListVector::const_iterator iter = m_Edges.begin();
			iter != m_Edges.end();
			++iter)
		{
			tot += iter->size();
		}
		return tot;
	}
	
	//当图是有向图时，返回真
	bool isDigraph()const{ return m_bDigraph;}

	//当图是空是，返回真
	bool isEmpty()const{ return m_Nodes.empty();}

	//当该点存在时，返回真
	bool isNodePresent(int idx)const;

	//当该边存在时，返回真
	bool isEdgePresent(int from, int to)const;

	//清空数据
	void Clear(){m_Nodes.clear(); m_Edges.clear(); m_iNextNodeIndex = 0;}

	//non-const的嵌套类迭代器
	//遍历某个顶点的相关边
	class EdgeIterator
	{
	private:
		//一些变量的定义
		typename EdgeList::iterator			curEdge;
		SparseGraph<node_type, edge_type>&	G;
		const int							NodeIndex;
	public:
		//对指定顶点经行迭代
		EdgeIterator(SparseGraph<node_type, edge_type>& graph,
			int node):
		G(graph),NodeIndex(node)
		{
			curEdge = G.m_Edges[NodeIndex].begin();
		}

		//返回该顶点的首个邻接点
		EdgeType* begin()
		{
			curEdge = G.m_Edges[NodeIndex].begin();
			//assert(curEdge == NULL &&"<SparseGraph::EdgeIterator::begin>: 该节点不存在有效边");
			return &(*curEdge);
		}

		//返回该顶点的下一个邻接点
		EdgeType* next()
		{
			++curEdge;
			if(end())	return NULL;
			return &(*curEdge);
		}

		//判断当前邻接点是否是该顶点的最后一个
		//返回真则是，否则返回假
		bool end()
		{
			return (curEdge == G.m_Edges[NodeIndex].end());
		}
	};
	friend class EdgeIterator;

	//const的嵌套类迭代器
	//遍历某个顶点的相关边
	class ConstEdgeIterator
	{
	private:
		//一些变量的定义
		typename EdgeList::const_iterator	curEdge;
		const SparseGraph<node_type, edge_type>&	G;
		const int							NodeIndex;
	public:
		//对指定顶点经行迭代
		ConstEdgeIterator(const SparseGraph<node_type, edge_type>& graph,
			int node):
		G(graph),NodeIndex(node)
		{
			curEdge = G.m_Edges[NodeIndex].begin();
		}

		//返回该顶点的首个邻接点
		const EdgeType* begin()
		{
			curEdge = G.m_Edges[NodeIndex].begin();
			//assert(curEdge == NULL &&"<SparseGraph::EdgeIterator::begin>: 该节点不存在有效边");
			return &(*curEdge);
		}

		//返回该顶点的下一个邻接点
		const EdgeType* next()
		{
			++curEdge;
			if(end())	return NULL;
			return &(*curEdge);
		}

		//判断当前邻接点是否是该顶点的最后一个
		//返回真则是，否则返回假
		bool end()
		{
			return (curEdge == G.m_Edges[NodeIndex].end());
		}
	};
	friend class ConstEdgeIterator;

	//non-const的嵌套类迭代器
	//遍历顶点
	class NodeIterator
	{
	private:
		typename NodeVector::iterator		curNode;
		SparseGraph<node_type, edge_type>&	G;

		//将curNode更新到下一个有效的顶点
		void GetNextValidNode(typename NodeVector::iterator& it)
		{
			if(curNode == G.m_Nodes.end() || it->Index() != invalid_node_index)
				return;
			while( it->Index() == invalid_node_index)
			{
				++it;
				if(curNode == G.m_Nodes.end()) break;
			}
		}
	public:
		//初始化curNode为点集的第一个点
		NodeIterator(SparseGraph<node_type, edge_type> &graph):G(graph)
		{
			curNode = G.m_Nodes.begin();
			//确保起始值也是有效的
			while( it->Index() == invalid_node_index)
			{
				++it;
				if(curNode == G.m_Nodes.end()) break;
			}
		}

		node_type* begin()
		{
			curNode = G.m_Nodes.begin();
			//确保起始值也是有效的
			while( it->Index() == invalid_node_index)
			{
				++it;
				if(curNode == G.m_Nodes.end()) break;
			}
			return &(*curNode);
		}

		node_type* next()
		{
			++curNode;
			GetNextValidNode(curNode);
			if(end())
				return NULL;
			return &(*curNode);
		}

		bool end()
		{
			return curNode == G.m_Nodes.end();
		}
	};
	friend class NodeIterator;

	//const的嵌套类迭代器
	//遍历顶点
	class ConstNodeIterator
	{
	private:
		typename NodeVector::const_iterator	curNode;
		const SparseGraph<node_type, edge_type>&	G;

		//将curNode更新到下一个有效的顶点
		void GetNextValidNode(typename NodeVector::const_iterator& it)
		{
			if(curNode == G.m_Nodes.end() || it->Index() != invalid_node_index)
				return;
			while( it->Index() == invalid_node_index)
			{
				++it;
				if(curNode == G.m_Nodes.end()) break;
			}
		}
	public:
		//初始化curNode为点集的第一个点
		ConstNodeIterator(const SparseGraph<node_type, edge_type> &graph):G(graph)
		{
			curNode = G.m_Nodes.begin();
			while(curNode->Index() == invalid_node_index)
			{
				++curNode;
				if(curNode == G.m_Nodes.end()) break;
			}
		}

		const node_type* begin()
		{
			curNode = G.m_Nodes.begin();
			while(curNode->Index() == invalid_node_index)
			{
				++curNode;
				if(curNode == G.m_Nodes.end()) break;
			}
			return &(*curNode);
		}

		const node_type* next()
		{
			++curNode;
			GetNextValidNode(curNode);
			if(end())
				return NULL;
			return &(*curNode);
		}

		bool end()
		{
			return curNode == G.m_Nodes.end();
		}
	};
	friend class ConstNodeIterator;
};

//************************************
// 方法:			isEdgePresent
// 全名:  		SparseGraph<node_type, edge_type>::isEdgePresent
// 访问权限:		public 
// 返回类型:   	bool
// 限定符: 		const
// 参数: 		int from
// 参数: 		int to
//************************************
template<typename node_type, typename edge_type>
bool SparseGraph<node_type, edge_type>::isEdgePresent( int from, int to ) const
{
	//检查from和to顶点是否有效
	if(isNodePresent(from) && isNodePresent(to))
	{
		//从from的每一个邻接点开始查找to，找到返回真，否则返回假
		for(EdgeList::const_iterator curEdge = m_Edges[from].begin();
			curEdge != m_Edges[from].end();
			++curEdge)
		{
			if(curEdge->To() == to)
				return true;
		}
		return false;
	}
	return false;
}

//************************************
// 方法:			isNodePresent
// 全名:  		SparseGraph<node_type, edge_type>::isNodePresent
// 访问权限:		public 
// 返回类型:   	bool
// 限定符: 		const
// 参数: 		int idx
//************************************
template<typename node_type, typename edge_type>
bool SparseGraph<node_type, edge_type>::isNodePresent( int idx ) const
{
	//当一个顶点的索引无效或者其索引值大于顶点总数时，是无效的
	if( (m_Nodes[idx].Index() == invalid_node_index) || (idx > (int)m_Nodes.size()))
		return false;
	return true;
}

//************************************
// 方法:			SetEdgeCost
// 全名:  		SparseGraph<node_type, edge_type>::SetEdgeCost
// 访问权限:		public 
// 返回类型:   	void
// 限定符: 		
// 参数: 		int from
// 参数: 		int to
// 参数: 		double cost
//************************************
template<typename node_type, typename edge_type>
void SparseGraph<node_type, edge_type>::SetEdgeCost( int from, int to, double cost )
{
	assert((from < (int)m_Nodes.size()) && (to < (int)m_Nodes.size()) &&
		"<SparseGraph::SetEdgeCost>: 无效的顶点索引");

	//通过对from点的每一个边进行查找
	for(EdgeList::iterator curEdge = m_Edges[from].begin();
		curEdge != m_Edges[from].end();
		++curEdge)
	{
		if(curEdge->To() == to)
		{
			curEdge->SetCost(cost);
			break;
		}
	}

	assert("<SparseGraph::SetEdgeCost>: 查找的边不存在");
}

//************************************
// 方法:			RemoveEdge
// 全名:  		SparseGraph<node_type, edge_type>::RemoveEdge
// 访问权限:		public 
// 返回类型:   	void
// 限定符: 		
// 参数: 		int from
// 参数: 		int to
//************************************
template<typename node_type, typename edge_type>
void SparseGraph<node_type, edge_type>::RemoveEdge( int from, int to )
{
	assert( (from < (int)m_Edges.size() && (to < (int)m_Edges.size() &&
		"<SparseGraph::RemoveEdge>: 无效的顶点索引")));

	//无向图
	if(!m_bDigraph)
	{
		for(EdgeList::iterator curEdge = m_Edges[to].begin();
			curEdge != m_Edges[to].end();
			++curEdge)
		{
			//找到to到from的边
			if(curEdge->To() == from)
			{
				curEdge = m_Edges[to].erase(curEdge);
				break;
			}
		}
	}

	for(EdgeList::iterator curEdge = m_Edges[from].begin();
		curEdge != m_Edges[from].end();
		++curEdge)
	{
		//找到from到to的边
		if(curEdge->To() == to)
		{
			curEdge = m_Edges[from].erase(curEdge);
			break;
		}
	}
}

//************************************
// 方法:			UniqueEdge
// 全名:  		SparseGraph<node_type, edge_type>::UniqueEdge
// 访问权限:		private 
// 返回类型:   	bool
// 限定符: 		const
// 参数: 		int from
// 参数: 		int to
//************************************
template<typename node_type, typename edge_type>
bool SparseGraph<node_type, edge_type>::UniqueEdge( int from, int to ) const
{
	for(EdgeList::const_iterator curEdge = m_Edges[from].begin();
		curEdge != m_Edges[from].end();
		++curEdge)
	{
		if(curEdge->To() == to)
			return false;
	}
	return true;
}

//************************************
// 方法:			AddEdge
// 全名:  		SparseGraph<node_type, edge_type>::AddEdge
// 访问权限:		public 
// 返回类型:   	void
// 限定符: 		
// 参数: 		EdgeType edge
//************************************
template<typename node_type, typename edge_type>
void SparseGraph<node_type, edge_type>::AddEdge( EdgeType edge )
{
	assert((edge.From() < m_iNextNodeIndex)&&(edge.To() < m_iNextNodeIndex)&&
		"<SparseGraph::AddEdge>: 无效的顶点索引");

	//必须保证每一个顶点的索引为有效值
	if( m_Nodes[edge.From()].Index() != invalid_node_index &&
		m_Nodes[edge.To()].Index() != invalid_node_index)
	{
		//确保边不会重复的增加
		if(UniqueEdge(edge.From(), edge.To()))
		{
			m_Edges[edge.From()].push_back(edge);
		}
		//无向图
		if(!m_bDigraph)
		{
			//确保边不会重复的增加
			if(UniqueEdge(edge.To(), edge.From()))
			{
				//与edge相反的构造新的边
				EdgeType newEdge = edge;
				newEdge.SetFrom(edge.To());
				newEdge.SetTo(edge.From());
				//增加反向边为To的邻接点
				m_Edges[edge.To()].push_back(newEdge);
			}
		}
	}
}

//************************************
// 方法:			CullInvalidEdges
// 全名:  		SparseGraph<node_type, edge_type>::CullInvalidEdges
// 访问权限:		private 
// 返回类型:   	void
// 限定符: 		
//************************************
template<typename node_type, typename edge_type>
void SparseGraph<node_type, edge_type>::CullInvalidEdges()
{
	typename EdgeListVector::iterator edgeList;
	typename EdgeList::iterator edge;
	//使用蛮力法逐一的剔除其值无效的索引点
	for(edgeList= m_Edges.begin(); edgeList != m_Edges.end(); ++edgeList)
	{
		edge = edgeList->begin();
		while(edge !=edgeList->end())
		{
			if(m_Nodes[edge->To()].Index() == invalid_node_index ||
				m_Nodes[edge->From()].Index() == invalid_node_index)
				//注意此处，erase后返回的是下一个边得迭代器，
				//如果这里使用for循环，将再次增加迭代器，最终
				//导致错误
				edge = edgeList->erase(edge);
			else
				//没有通过erase来递进迭代器时，应显式增加迭代器
				++edge;
		}
	}
}

//************************************
// 方法:			RemoveNode
// 全名:  		SparseGraph<node_type, edge_type>::RemoveNode
// 访问权限:		public 
// 返回类型:   	void
// 限定符: 		
// 参数: 		int idx
//************************************
template<typename node_type, typename edge_type>
void SparseGraph<node_type, edge_type>::RemoveNode( int idx )
{
	assert((idx < (int)m_Nodes.size() &&
		"<SparseGraph::RemoveNode>无效的索引"));
	//先将该点的索引置为无效
	m_Nodes[idx].SetIndex(invalid_node_index);
	//无向图
	if(!m_bDigraph)
	{
		//访问每一个idx的邻接点，并且删除指向该点的任何一条边
		for(EdgeList::iterator curEdge = m_Edges[idx].begin();
			curEdge != m_Edges[idx].end();
			++curEdge)
		{
			for(EdgeList::iterator curE = m_Edges[curEdge->To()].begin();
				curE != m_Edges[curEdge->To()].end();
				++curE)
			{
				//找到
				if(curE->To() == idx)
				{
					curE = m_Edges[curEdge->To()].erase(curE);
					break;
				}
			}
		}
		m_Edges[idx].clear();
	}
	//有向图
	else
	{
		CullInvalidEdges();
	}
}

//************************************
// 方法:			AddNode
// 全名:  		SparseGraph<node_type, edge_type>::AddNode
// 访问权限:		public 
// 返回类型:   	int
// 限定符: 		
// 参数: 		NodeType node
//************************************
template<typename node_type, typename edge_type>
int SparseGraph<node_type, edge_type>::AddNode( NodeType node )
{
	if(node.Index() < (int)m_Nodes.size())
	{
		//确保每一个顶点的索引都是唯一的
		assert((m_Nodes[node.Index()].Index() == invalid_node_index) &&
			"<SparseGraph::AddNode>: 正在尝试增加相同索引的节点");

		m_Nodes[node.Index()] = node;
		return m_iNextNodeIndex;
	}
	else
	{
		//应该保证增加的顶点有效
		assert(node.Index() == m_iNextNodeIndex &&
			"<SparseGraph::AddNode>: 正在尝试增加一个无效的节点");

		m_Nodes.push_back(node);
		m_Edges.push_back(EdgeList());
		return m_iNextNodeIndex++;
	}
}

//************************************
// 方法:			GetEdge
// 全名:  		SparseGraph<node_type, edge_type>::GetEdge
// 访问权限:		public 
// 返回类型:   	edge_type&
// 限定符: 		
// 参数: 		int from
// 参数: 		int to
//************************************
template<typename node_type, typename edge_type>
edge_type& SparseGraph<node_type, edge_type>::GetEdge( int from, int to )
{
	assert( (from < (int)m_Edges.size())&&
		(from >= 0)&&
		"<SparseGraph::GetEdge>: ‘From’索引无效");

	assert( (to < (int)m_Edges.size())&&
		(to >= 0)&&
		"<SparseGraph::GetEdge>: ‘To’索引无效");

	for(EdgeList::iterator iter = m_Edges[from].begin();
		iter != m_Edges[from].end();
		++iter)
	{
		if(iter->To() == to)	return *iter;
	}
	assert (0 && "<SparseGraph::GetEdge>: 查找的边不存在");
}

//************************************
// 方法:			GetEdge
// 全名:  		SparseGraph<node_type, edge_type>::GetEdge
// 访问权限:		public 
// 返回类型:   	const edge_type&
// 限定符: 		const
// 参数: 		int from
// 参数: 		int to
//************************************
template<typename node_type, typename edge_type>
const edge_type& SparseGraph<node_type, edge_type>::GetEdge( int from, int to ) const
{
	assert( (from < m_Edges.size())&&
		(from >= 0)&&
		"<SparseGraph::GetEdge>: ‘From’索引无效");

	assert( (to < m_Edges.size())&&
		(to >= 0)&&
		"<SparseGraph::GetEdge>: ‘To’索引无效");

	for(EdgeList::const_iterator iter = m_Edges[from].begin();
		iter != m_Edges[from].end();
		++iter)
	{
		if(iter->To() == to)	return *iter;
	}

	assert (0 && "<SparseGraph::GetEdge>: 查找的边不存在");
}

//************************************
// 方法:			GetNode
// 全名:  		SparseGraph<node_type, edge_type>::GetNode
// 访问权限:		public 
// 返回类型:   	node_type&
// 限定符: 		
// 参数: 		int idx
//************************************
template<typename node_type, typename edge_type>
node_type& SparseGraph<node_type, edge_type>::GetNode( int idx )
{
	assert((idx < (int)m_Nodes.size()) &&
		(idx >= 0)&&
		"<SparseGraph::GetNode>: 无效索引");

	return m_Nodes[idx];
}

//************************************
// 方法:			GetNode
// 全名:  		SparseGraph<node_type, edge_type>::GetNode
// 访问权限:		public 
// 返回类型:   	const node_type&
// 限定符: 		const
// 参数: 		int idx
//************************************
template<typename node_type, typename edge_type>
const node_type& SparseGraph<node_type, edge_type>::GetNode( int idx ) const
{
	assert((idx < (int)m_Nodes.size()) &&
		(idx >= 0)&&
		"<SparseGraph::GetNode>: 无效索引");

	return m_Nodes[idx];
}

#endif // SparseGraph_h__